# 解法 1 的 cache 版
class Solution:
    def __init__(self):
        self.cache = {}

    def uniquePaths(self, m: int, n: int) -> int:
        return self.upc(m, n)

    def upc(self, m, n):
        t = (m, n)
        if t in self.cache:
            return self.cache[t]
        else:
            r = self.up(m, n)
            self.cache[t] = r
            self.cache[(n ,m)] = r # 左右对称
            return r

    def up(self, m, n):
        if m > 1 and n > 1:
            return self.upc(m - 1, n) + self.upc(m, n - 1)
        return 1

solu = Solution()
print(solu.uniquePaths(3, 2))